#include "../constant.h"
#include "./bitree.h"

#include <stack>
#include <queue>
using namespace std;

void LevelOrder(BiTree T)
{
    queue<BiTNode *> q;
    q.push(T);
    while (!q.empty())
    {
        Visit(q.front());
        if (q.front()->lchild)
            q.push(q.front()->lchild);
        if (q.front()->rchild)
            q.push(q.front()->rchild);
        q.pop();
    }
    printf("\n");
}

// 借助两个栈，将“左右根”转化成“根右左”，遍历更简单
void PostOrderNonRecursive(BiTree T)
{
    if (T == NULL)
        return;
    stack<BiTNode *> s;
    stack<BiTNode *> res; // res栈存储根右左，然后弹出就是左右根
    BiTree p = T;
    while (!s.empty() || p != 0)
    {
        if (p)
        {
            s.push(p);
            res.push(p); // 重定向输出到res栈
            p = p->rchild;
        }
        else
        {
            p = s.top();
            s.pop();
            p = p->lchild;
        }
    }
    while (!res.empty())
    {
        Visit(res.top());
        res.pop();
    }
    printf("\n");
}

void PreOrderNonRecursive(BiTree T)
{
    stack<BiTNode *> s;
    BiTNode *p = T;
    while (!s.empty() || p != NULL)
    {
        if (p != NULL)
        {
            Visit(p);  // 前序，先输出根
            s.push(p); // 入栈是因为需要通过根节点找到右节点
            p = p->lchild;
        }
        else
        {
            // 已经到了“最左下角”，该遍历右子节点了，这里就不输出当前节点（根节点）了
            p = s.top();
            s.pop();
            p = p->rchild;
        }
    }
    printf("\n");
}

void InOrderNonRecursive(BiTree T)
{
    stack<BiTNode *> s;
    BiTNode *p = T;
    while (!s.empty() || p != NULL)
    {
        if (p != NULL)
        {
            s.push(p); // 一直入栈 寻找最左下角的节点
            p = p->lchild;
        }
        else
        {
            p = s.top(); // 最左下角的节点
            s.pop();
            Visit(p);
            p = p->rchild; // 当前节点相当于没有左子节点的根节点，此时应当访问其右节点
        }
    }
    printf("\n");
}

void PostOrder(BiTree T)
{
    if (T == NULL)
        return;
    PostOrder(T->lchild);
    PostOrder(T->rchild);
    Visit(T);
}

void InOrder(BiTree T)
{
    if (T == NULL)
        return;
    InOrder(T->lchild);
    Visit(T);
    InOrder(T->rchild);
}

void PreOrder(BiTree T)
{
    if (T == NULL)
        return;
    Visit(T);
    PreOrder(T->lchild);
    PreOrder(T->rchild);
}

void Visit(BiTree node)
{
    printf("%c", node->data);
}